
<!DOCTYPE html>
<!--[if IEMobile 7 ]><html class="no-js iem7"><![endif]-->
<!--[if lt IE 9]><html class="no-js lte-ie8"><![endif]-->
<!--[if (gt IE 8)|(gt IEMobile 7)|!(IEMobile)|!(IE)]><!--><html class="no-js" lang="en"><!--<![endif]-->
<head>
  <meta charset="utf-8">
  <title>Yebangyu's Blog</title>
  <meta name="author" content="Yebangyu">

  
  <meta name="description" content="本文将对快速排序进行深入的分析和介绍。通过学习本文，您将 秒杀快速排序面试 掌握高效实现快排 加深范型编程意识 八卦花絮 快速排序是由图灵奖获得者、计算机语言设计大佬C. A. R. Hoare在他26岁时提出的。说起C. A. R. Hoare老爷爷，可能很多人的第一印象就是快速排序， &hellip;">
  

  <!-- http://t.co/dKP3o1e -->
  <meta name="HandheldFriendly" content="True">
  <meta name="MobileOptimized" content="320">
  <meta name="viewport" content="width=device-width, initial-scale=1">

  
  <link rel="canonical" href="http://www.yebangyu.org/posts/3/">
  <link href="/favicon.png" rel="icon">
  <link href="/stylesheets/screen.css" media="screen, projection" rel="stylesheet" type="text/css">
  <link href="/atom.xml" rel="alternate" title="Yebangyu's Blog" type="application/atom+xml">
  <script src="/javascripts/modernizr-2.0.js"></script>
  <script src="//ajax.lug.ustc.edu.cn/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
  <script>!window.jQuery && document.write(unescape('%3Cscript src="/javascripts/libs/jquery.min.js"%3E%3C/script%3E'))</script>
  <script src="/javascripts/octopress.js" type="text/javascript"></script>
  <!--Fonts from Google"s Web font directory at http://google.com/webfonts -->
<link href="//fonts.lug.ustc.edu.cn/css?family=PT+Serif:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<link href="//fonts.lug.ustc.edu.cn/css?family=PT+Sans:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  jax: ["input/TeX", "output/HTML-CSS"],
  tex2jax: {
    inlineMath: [ ['$', '$'] ],
    displayMath: [ ['$$', '$$']],
    processEscapes: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
  },
  messageStyle: "none",
  "HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"] }
});
</script>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML" type="text/javascript"></script>

  

</head>

<body   >
  <header role="banner"><hgroup>
  <h1><a href="/">Yebangyu's Blog</a></h1>
  
    <h2>Fond of Concurrency Programming and Machine Learning</h2>
  
</hgroup>

</header>
  <nav role="navigation"><ul class="subscription" data-subscription="rss">
  <li><a href="/atom.xml" rel="subscribe-rss" title="subscribe via RSS">RSS</a></li>
  
</ul>
  
<form action="https://www.google.com/search" method="get">
  <fieldset role="search">
    <input type="hidden" name="sitesearch" value="www.yebangyu.org">
    <input class="search" type="text" name="q" results="0" placeholder="Search"/>
  </fieldset>
</form>
  
<ul class="main-navigation">
  <li><a href="/">Blog</a></li>
  <li><a href="/blog/archives">Archives</a></li>
  <li><a href="/about">About Me</a></li>
</ul>

</nav>
  <div id="main">
    <div id="content">
      <div class="blog-index">
  
  
  
    <article>
      
  <header>
    
      <h1 class="entry-title"><a href="/blog/2016/03/09/quicksort/">深入解析快速排序(Quick Sort)</a></h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-03-09T22:34:14+08:00'><span class='date'><span class='date-month'>Mar</span> <span class='date-day'>9</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>10:34 pm</span></time>
        
      </p>
    
  </header>


  <div class="entry-content"><p>本文将对快速排序进行深入的分析和介绍。通过学习本文，您将</p>

<blockquote>
  <ul>
    <li>秒杀快速排序面试</li>
    <li>掌握高效实现快排</li>
    <li>加深范型编程意识</li>
  </ul>
</blockquote>

<h2 id="section">八卦花絮</h2>

<p>快速排序是由图灵奖获得者、计算机语言设计大佬C. A. R. Hoare在他26岁时提出的。说起C. A. R. Hoare老爷爷，可能很多人的第一印象就是快速排序，但是快排仅仅是他人生中非常小的成就而已。例如，他在1978年提出的Communicating Sequential Processes(CSP)理论，则深深的影响了并行程序设计，Go语言中的Goroutine就是这种典范。</p>

</div>
  
  
    <footer>
      <a rel="full-article" href="/blog/2016/03/09/quicksort/">阅读更多 →</a>
    </footer>
  


    </article>
  
  
    <article>
      
  <header>
    
      <h1 class="entry-title"><a href="/blog/2016/03/04/petersonalgorithm/">Peterson算法实现spin lock</a></h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-03-04T22:26:51+08:00'><span class='date'><span class='date-month'>Mar</span> <span class='date-day'>4</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>10:26 pm</span></time>
        
      </p>
    
  </header>


  <div class="entry-content"><p>对spin lock和mutex不熟悉的朋友，可以看<a href="http://www.yebangyu.org/blog/2016/01/24/spinlock-and-mutex/">上篇</a>博客。</p>

<h2 id="section">提出问题</h2>

<p>如何仅仅通过load和store实现spin lock呢？</p>

<p>本文只考虑、只针对只有两个线程的情形。假设这两个线程的id分别为0和1。编程环境为X86体系结构 + Intel CPU + gcc</p>

</div>
  
  
    <footer>
      <a rel="full-article" href="/blog/2016/03/04/petersonalgorithm/">阅读更多 →</a>
    </footer>
  


    </article>
  
  
    <article>
      
  <header>
    
      <h1 class="entry-title"><a href="/blog/2016/02/24/writeelegantcodes/">编写高质量代码(下)</a></h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-02-24T22:26:44+08:00'><span class='date'><span class='date-month'>Feb</span> <span class='date-day'>24</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>10:26 pm</span></time>
        
      </p>
    
  </header>


  <div class="entry-content"><p><a href="http://www.yebangyu.org/blog/2015/11/06/how-to-write-elegant-cpp-codes/">上回</a>我们从微观角度，以一个实际的例子，从正确、高效、易读等特性着手，介绍了如何编写高质量的代码。这次，我们从宏观出发，从软件开发流程入手，着重介绍其中的几个方面，包括代码规范、Code Review、测试等。</p>

<p>如果说<a href="http://www.yebangyu.org/blog/2015/11/06/how-to-write-elegant-cpp-codes/">上回</a>的内容注重个人编码，那么本文将偏向团队开发。</p>

<h2 id="section">代码规范</h2>

<p>团队的代码规范，一般由领导和大佬们制定后，大家统一实行。这里面有几个问题：</p>

<h3 id="section-1">真的需要代码规范吗？</h3>

<p>言下之意，制定和执行代码规范是否浪费时间？</p>

</div>
  
  
    <footer>
      <a rel="full-article" href="/blog/2016/02/24/writeelegantcodes/">阅读更多 →</a>
    </footer>
  


    </article>
  
  
    <article>
      
  <header>
    
      <h1 class="entry-title"><a href="/blog/2016/02/20/object-function-in-cpp/">C++函数对象(function object)的应用</a></h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-02-20T23:30:53+08:00'><span class='date'><span class='date-month'>Feb</span> <span class='date-day'>20</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>11:30 pm</span></time>
        
      </p>
    
  </header>


  <div class="entry-content"><p>假如我们实现了这样的一个单向链表：</p>
<div class="bogus-wrapper"><notextile><figure class="code"><figcaption><span></span></figcaption><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class="line-number">1</span>
<span class="line-number">2</span>
<span class="line-number">3</span>
<span class="line-number">4</span>
<span class="line-number">5</span>
<span class="line-number">6</span>
<span class="line-number">7</span>
<span class="line-number">8</span>
<span class="line-number">9</span>
<span class="line-number">10</span>
<span class="line-number">11</span>
<span class="line-number">12</span>
<span class="line-number">13</span>
</pre></td><td class="code"><pre><code class="c++"><span class="line"><span class="k">class</span> <span class="nc">LinkedListNode</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="kt">int</span> <span class="n">data_</span><span class="p">;</span>
</span><span class="line">  <span class="n">LinkedListNode</span> <span class="o">*</span><span class="n">next_</span><span class="p">;</span>
</span><span class="line"><span class="p">};</span>
</span><span class="line"><span class="k">class</span> <span class="nc">LinkedList</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="k">public</span><span class="o">:</span>
</span><span class="line">    <span class="kt">void</span> <span class="n">insert</span><span class="p">(</span><span class="n">LinkedListNode</span><span class="o">*</span> <span class="o">&amp;</span><span class="n">p</span><span class="p">);</span>
</span><span class="line">    <span class="kt">void</span> <span class="nf">del</span><span class="p">(</span><span class="n">LinkedListNode</span> <span class="o">*</span><span class="n">p</span><span class="p">);</span>
</span><span class="line">  <span class="k">private</span><span class="o">:</span>
</span><span class="line">    <span class="n">LinkedListNode</span> <span class="o">*</span><span class="n">head_</span><span class="p">;</span>
</span><span class="line"><span class="p">};</span>
</span></code></pre></td></tr></table></div></figure></notextile></div>
</div>
  
  
    <footer>
      <a rel="full-article" href="/blog/2016/02/20/object-function-in-cpp/">阅读更多 →</a>
    </footer>
  


    </article>
  
  
    <article>
      
  <header>
    
      <h1 class="entry-title"><a href="/blog/2016/02/16/materials-in-concurrency-programming/">Materials In Concurrency Programming</a></h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-02-16T23:36:28+08:00'><span class='date'><span class='date-month'>Feb</span> <span class='date-day'>16</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>11:36 pm</span></time>
        
      </p>
    
  </header>


  <div class="entry-content"><h2 id="prerequisite">Prerequisite</h2>

<p>对CPU、内存、Cache有一个很好的认识，对学习并发编程有很大的帮助。</p>

<p><a href="https://people.freebsd.org/~lstewart/articles/cpumemory.pdf">What Every Programmer Should Know About Memory</a></p>

<p><a href="http://www.amazon.com/Consistency-Coherence-Synthesis-Lectures-Architecture/dp/1608455645">A Primer on Memory Consistency and Cache Coherence</a></p>

</div>
  
  
    <footer>
      <a rel="full-article" href="/blog/2016/02/16/materials-in-concurrency-programming/">阅读更多 →</a>
    </footer>
  


    </article>
  
  
    <article>
      
  <header>
    
      <h1 class="entry-title"><a href="/blog/2016/02/01/detectmemoryghostinmultithread/">多线程内存问题分析之mprotect方法</a></h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-02-01T22:24:25+08:00'><span class='date'><span class='date-month'>Feb</span> <span class='date-day'>1</span><span class='date-suffix'>st</span>, <span class='date-year'>2016</span></span> <span class='time'>10:24 pm</span></time>
        
      </p>
    
  </header>


  <div class="entry-content"><p>多线程中的内存问题，一直被认为是噩梦般的存在，几乎只有高手、大仙才能解决。除了大量的打log、gdb调试、code review以及依靠多年的经验和直觉之外，有没有一些分析的手段和工具呢？答案是肯定的。本文首先介绍其中的一种：mprotect大法。通过mprotect，保护特定的感兴趣的内存，当有线程改写该区域时，会产生一个中断，我们在中断处理函数中把调用栈等信息打印出来。这是大概的思路，不过其中的问题很多，我们慢慢道来。</p>

</div>
  
  
    <footer>
      <a rel="full-article" href="/blog/2016/02/01/detectmemoryghostinmultithread/">阅读更多 →</a>
    </footer>
  


    </article>
  
  
    <article>
      
  <header>
    
      <h1 class="entry-title"><a href="/blog/2016/01/29/insidethebloomfilter/">深入解析Bloom Filter(中)</a></h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-01-29T22:38:31+08:00'><span class='date'><span class='date-month'>Jan</span> <span class='date-day'>29</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>10:38 pm</span></time>
        
      </p>
    
  </header>


  <div class="entry-content"><p>本篇将介绍：</p>

<blockquote>
  <ul>
    <li>d-left hashing</li>
    <li>d-left counting bloom filter</li>
  </ul>
</blockquote>

<p>在<a href="http://www.yebangyu.org/blog/2016/01/23/insidethebloomfilter/">上篇</a>文章，我们介绍了Standard Bloom Filter(SBF)和Counting Bloom Filter(CBF)。简单回顾下，我们大概思路和历程是：为了解决允许false positive下的membership问题，我们设计了哈希表算法，由于它所需空间巨大，我们引入bitmap方法；因为它false positive possibility太大，我们引入了SBF，它使用多个独立的、均匀分布的哈希函数。而SBF的一个缺点是不支持删除操作，为了能够删除，我们引入了CBF，然而，CBF存在一个问题。</p>

<p>什么问题呢？那就是空间利用率不高。这可以通过简单的数学计算知道大概：</p>

<p>考察某个位置，该位置的计数器counter的值$\xi$</p>

<p>$P(\xi = c) \approx \binom{mk}{c} {(\frac{1}{n})}^{c}({1-\frac{1}{n}})^{mk-c} = B(km,\frac{1}{n})$</p>

</div>
  
  
    <footer>
      <a rel="full-article" href="/blog/2016/01/29/insidethebloomfilter/">阅读更多 →</a>
    </footer>
  


    </article>
  
  
    <article>
      
  <header>
    
      <h1 class="entry-title"><a href="/blog/2016/01/24/spinlock-and-mutex/">Spinlock and mutex</a></h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-01-24T15:50:31+08:00'><span class='date'><span class='date-month'>Jan</span> <span class='date-day'>24</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>3:50 pm</span></time>
        
      </p>
    
  </header>


  <div class="entry-content"><p>Spinlock（自旋锁）和mutex作为两种互斥锁，在并行编程中都得到了广泛应用。那么，这两种锁有什么区别吗？</p>

<p>当一个线程对Spinlock加锁时，如果该锁被其他线程占用，那么该线程会通过一个loop不断地重试（ try again and again）；而使用mutex的线程没有得到锁时，会sleep。</p>

<p>因为，当临界区较短时，Spinlock因为没有上下文切换，可能性能更优；当临界区较长时，不断的spin将浪费大量的cpu资源。</p>

</div>
  
  
    <footer>
      <a rel="full-article" href="/blog/2016/01/24/spinlock-and-mutex/">阅读更多 →</a>
    </footer>
  


    </article>
  
  
    <article>
      
  <header>
    
      <h1 class="entry-title"><a href="/blog/2016/01/23/insidethebloomfilter/">深入解析Bloom Filter(上)</a></h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-01-23T13:24:49+08:00'><span class='date'><span class='date-month'>Jan</span> <span class='date-day'>23</span><span class='date-suffix'>rd</span>, <span class='date-year'>2016</span></span> <span class='time'>1:24 pm</span></time>
        
      </p>
    
  </header>


  <div class="entry-content"><p>本文将介绍：</p>

<blockquote>
  <ul>
    <li>Bloom Filter和它的变形与拓展</li>
    <li>Bloom Filter的使用场景</li>
    <li>Bloom Filter的详细数学分析</li>
  </ul>
</blockquote>

<h2 id="section">提出问题</h2>

<p>Google的爬虫每天需要抓取大量的网页。于是就有一个问题：每当爬虫分析出一个url的时候，是抓呢，还是不抓呢？如何知道这个url已经爬过了？</p>

</div>
  
  
    <footer>
      <a rel="full-article" href="/blog/2016/01/23/insidethebloomfilter/">阅读更多 →</a>
    </footer>
  


    </article>
  
  
    <article>
      
  <header>
    
      <h1 class="entry-title"><a href="/blog/2016/01/17/concurrenyandparallism/">Concurrent and Parallel</a></h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-01-17T09:49:00+08:00'><span class='date'><span class='date-month'>Jan</span> <span class='date-day'>17</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>9:49 am</span></time>
        
      </p>
    
  </header>


  <div class="entry-content"><p>什么是并发(<strong>Concurrency，Concurrent</strong>)，什么是并行(<strong>parallism，Parallel</strong>)？这两者有什么区别？本文收录一下我听过的、我见过的、我看过的一些人的看法。仅供参考：</p>

<h2 id="paul-butcher">Paul Butcher</h2>

<p><strong>Paul Butcher</strong>在他的《<strong>Seven Concurrency Models in Seven Weeks</strong>
》里开篇就谈到：</p>

</div>
  
  
    <footer>
      <a rel="full-article" href="/blog/2016/01/17/concurrenyandparallism/">阅读更多 →</a>
    </footer>
  


    </article>
  
  <div class="pagination">
    
      <a class="prev" href="/posts/4">&larr; Older</a>
    
    <a href="/blog/archives">Blog Archives</a>
    
    <a class="next" href="/posts/2">Newer &rarr;</a>
    
  </div>
</div>
<aside class="sidebar">
  
    <section>
  <h1>Recent Posts</h1>
  <ul id="recent_posts">
    
      <li class="post">
        <a href="/blog/2017/03/11/2017/">2017技术成长之路</a>
      </li>
    
      <li class="post">
        <a href="/blog/2017/02/17/virtualfunctionandvariadicparametertemplate/">虚函数和变长参数模板的妙用</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/25/singleton/">Singleton与多线程</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/04/introductiontohazardpointer/">Lock Free中的Hazard Pointer(下)</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/03/gccandperfopt/">性能优化的那些传说和迷思</a>
      </li>
    
  </ul>
</section>
<section>
  <h1>Friends' Link</h1>
  <ul>
    <li>
	  <li><a href="http://www.chongh.wiki/">Diting0x</a></li>
	  <li><a href="http://www.xiaolili.net/">wangli</a></li>
	  <li><a href="http://www.skykewei.top">dukewei</a></li>
	  <li><a href="http://irwenqiang.github.io">chenwenqiang</a></li>
      <li><a href="http://www.armsword.com">duruofei</a></li>
    </li>
  </ul>
</section><section>
  <h1>Yebangyu</h1>
  <p>福建人。热爱历史、K歌、NBA</p>
  <p>帝都码农</p>
  <p>历史学家，专治秦汉史</p>
</section>
<section>
 <h1>Categories</h1>
 <ul id="categories">
  <li class='category'><a href='/blog/categories/c-plus-plus/'>c++ (11)</a></li>
<li class='category'><a href='/blog/categories/soupen/'>soupen (4)</a></li>
<li class='category'><a href='/blog/categories/web/'>web (1)</a></li>
<li class='category'><a href='/blog/categories/qi-ta/'>其他 (5)</a></li>
<li class='category'><a href='/blog/categories/li-shi/'>历史 (2)</a></li>
<li class='category'><a href='/blog/categories/bing-xing-bian-cheng/'>并行编程 (20)</a></li>
<li class='category'><a href='/blog/categories/xing-neng-you-hua/'>性能优化 (2)</a></li>
<li class='category'><a href='/blog/categories/suan-fa/'>算法 (4)</a></li>
<li class='category'><a href='/blog/categories/bian-yi-lian-jie/'>编译链接 (2)</a></li>

 </ul>
</section>




  
</aside>

    </div>
  </div>
  <footer role="contentinfo"><!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  jax: ["input/TeX", "output/HTML-CSS"],
  tex2jax: {
    inlineMath: [ ['$', '$'] ],
    displayMath: [ ['$$', '$$']],
    processEscapes: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
  },
  messageStyle: "none",
  "HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"] }
});
</script>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML" type="text/javascript"></script>
<p>
  Copyright &copy; 2017 - Yebangyu -
  <span class="credit">Powered by <a href="http://octopress.org">Octopress</a></span>
</p>
<script type="text/javascript">var cnzz_protocol = (("https:" == document.location.protocol) ? " https://" : " http://");document.write(unescape("%3Cspan id='cnzz_stat_icon_1257548193'%3E%3C/span%3E%3Cscript src='" + cnzz_protocol + "s11.cnzz.com/z_stat.php%3Fid%3D1257548193' type='text/javascript'%3E%3C/script%3E"));</script>

</footer>
  











</body>
</html>
